A Reed-Solomon code is an algebraic transformation for encoding a message so that it can be sent through a noisy environment and recovered accurately, even though errors are introduced into the message. Reed-Solomon codes have been used for wide variety of applications such as satellite communications, compact disc playback and asynchronous digital subscriber line (xe2x80x9cADSLxe2x80x9d) communications. A discussion of the wide range of applications for Reed-Solomon codes is found in Stephen B. Wicker and Vijay K. Bhargava, Reed-Solomon Codes and Their Applications (IEEE Press 1994).
The mathematical foundation for Reed-Solomon encoding is a finite field known as a Galois Field (xe2x80x9cGFxe2x80x9d). An introduction to finite field algebra is found in Shu Lin and Daniel J. Costello, Jr., Error Control Coding: Fundamentals and Applications, pp. 15 et seq. (Prentice-Hall 1983) (xe2x80x9cLin and Costelloxe2x80x9d). A Galois Field of 2m elements (xe2x80x9cGF(2m)xe2x80x9d) is generated from a xe2x80x9cprimitivexe2x80x9d polynomial. Adding or multiplying two of the largest elements of the field together produces a smaller element, because the field is finite. Galois Field GF(2m) addition is modulo-2 addition and is indicated by ⊕.
Reed-Solomon encoding takes place in a field of 2m elements. A Reed-Solomon encoded message is divided into code words or segments of 2mxe2x88x921 or fewer symbols, each symbol represented by m bits. A code word having fewer than 2mxe2x88x921 symbols is referred to as a shortened code. The xe2x80x9csymbolsxe2x80x9d represent elements of the finite field which, after a fashion, can be added or multiplied together. By one convention, the elements of the field are denoted 0, 1, xcex1, xcex12 . . . xcex12mxe2x88x922, where xcex1 and the primitive polynomial p(x) are related by the equation p(xcex1)=0.
One of the useful properties of a Reed-Solomon code is that it is well adapted to parallel processing. Efforts have been made to design parallel processors or systolic arrays to decode Reed-Solomon codes, including efforts by Shao and Reed. Howard M. Shao, T. K. Truong, Leslie J. Deutsch, Joseph H. Yueng and Irving S. Reed, xe2x80x9cA VLSI Design of a Pipeline Reed-Solomon Decoder,xe2x80x9d IEEE Transactions on Computers, Vol. C-34, No. 5, pp. 393-401 (May 1985); Howard M. Shao and Irving S. Reed, xe2x80x9cOn the VLSI Design of the Reed-Solomon Decoder Using Systolic Arrays,xe2x80x9d IEEE Transactions on Computers, Vol. C-37, No. 10, pp. 1273-78 (October 1988). Another well-known decoder was designed by Elwyn Berlekamp and his colleagues. Elwyn Berlekamp, Gadiel Seroussi, Po Tong, xe2x80x9cA Hypersystolic Reed-Solomon Decoder,xe2x80x9d Chapter 10 in Wicker and Bhargava, Reed-Solomon Codes and Their Applications, p. 205 et seq. (xe2x80x9cChapter 10xe2x80x9d); E. R. Berlekamp, G. Seroussi, and P. Tong, Hypersystolic Reed-Solomon Decoder, U.S. Pat. No. 4,958,348, issued Sep. 18, 1990.
Reed-Solomon decoding generally involves four steps. In the first two steps, a syndrome polynomal S(x) is generated and the key equation xcex9(x)S(x)=xcexa9(x) mod x2t is solved to obtain an error location polynomial xcex9(x) and an error evaluator polynomial xcexa9(x). Step three is to evaluate these polynomials to determine which symbols are affected by errors and what are the error values, resulting in an error polynomial E(x). Finally, the error polynomial is combined with the received polynomial R(x) (which is buffered during steps one to three) to produce a reconstructed message without errors.
One of the tools for generating error location and error evaluator ploynomals is Euclid""s algorithm. However, Euclid""s algorithm involves division in a finite field or multiplication by a multiplicative inverse. A significant contribution of Shao and Reed was to implement a modified Euclid""s algorithm to find an error-location polynomial without computation of inverse elements. Berlekamp uses cross-multiplication instead of division in his extended Euclid""s algorithm. Chapter 10, pp. 221-22. In addition, Berlekamp introduces a xe2x80x9chypersystolicxe2x80x9d architecture, by which he means that clock signals are part of the data that passes from one computation cell to another, thereby reducing the dependence of parallel processing computation cells on synchronized propagation of a clock signal. Use of cross-multiplication increases processing time or the number of multipliers required in each cell. Hypersystolic architecture increases the number of steps required to produce a result, as data passes in a special serial sequence up and down each of Berlekamp""s towers and from one tower to the next, twice through each cell.
An advantageous design would directly apply Euclid""s algorithm using a single divider, sharing the results, and thereby minimizing the number of dividers required. A shared divider design for the second step of Reed-Solomon decoding would enable parallel processing of each symbol or term of a code word. The number of clock cycles required to apply Euclid""s algorithm would be minimized, resulting in either faster processing or use of a slower clock speed with resulting cost reductions.
Another aspect of an advantageous design would be to evaluate both the error location and error evaluator polynomial simultaneously in a minimum number of cycles. The overall objective is to minimize the complexity and number of computation cells, thereby reducing the foot print of the decoder circuit, reducing its cost and speeding signal processing.
One aspect of the present invention is a method and device for calculation of syndromes, useful in decoding a Reed-Solomon (N, K) encoded message with m-bit symbols, including a set of 2t syndrome calculation cells coupled to inputs and outputs, where the syndrome calculation cells include a syndrome register coupled to an output, a constant multiplier with its input coupled to the syndrome register, an adder with inputs coupled to the serial input and the constant multiplier, and a mux with its inputs coupled to xe2x80x9c0xe2x80x9d and to the adder and its output coupled to the syndrome register, where the mux is responsive to a syndrome calculate signal.
A second aspect of the present invention is a method and device to divide polynomials over a Galois Field, useful in decoding a Reed-Solomon (N, K) encoded message with m-bit symbols, including a dividend polynomial array of first cells, the first cells coupled with the next lower order first cell, a divisor polynomial array of second cells, the second cells coupled with the next lower order second cell, a shared divider for calculating the highest order first cell divided by the highest order second cell, its output coupled to the first cells, and logic to calculate a quotient of the highest order first cell divided by the highest order second cell and a remainder polynomial of the dividend polynomial minus said quotient times the divisor polynomial. The present invention is adapted to produce a quotient and remainder in a single clock cycle. It may include a product polynomial array of third cells, the third cell coupled to its next lower order third cell and to the shared divider. The present invention can be practiced with only one multiplier per first cell and no multipliers in the second and third cells.
Another aspect of the present invention is a method and device to apply Euclid""s algorithim to decode a Reed-Solomon (N, K) encoded message of m-bit symbols and corresponding syndromes, where N less than =2mxe2x88x921 and Nxe2x88x92K=2t, including a dividend polynomial array of first cells, the first cells coupled to the next lower order first cells, a divisor polynomial array of second cells, the second cells coupled to the same and next higher order first cells and to the next lower order second cell, an array of third cells, the third cell coupled to the same order first and second cells and to the next lower order third cell, a shared divider with its inputs coupled to the highest order first and second cells and its output coupled to the first cells, and logic to calculate a quotient of the highest order first cell divided by the highest order second cell and a remainder polynomial of the dividend polynomial minus said quotient times the divisor polynomial.
Yet another aspect of the present invention is a method and device to apply Euclid""s algorithm to decode a Reed-Solomon (N, K) encoded message of m-bit symbols and corresponding syndromes S(x), where N less than =2mxe2x88x921 and Nxe2x88x92K=2t, including arrays of first, second and third cells, a shared divider coupled to the array, which divides the highest order first and second cells and outputs a quotient to the first cells, logic to partition the first cells to represent polynomials xcexa9(kxe2x88x922)(x) and xcex9(kxe2x88x922)(x) and to partition the second cells to represent polynomials xcexa9(kxe2x88x921)(x) and xcex9(kxe2x88x921)(x), where k is an index of iteration, and logic to calculate xcex9(k)(x)=xcex9(kxe2x88x922)(x)xe2x88x92[Q(k)(x){circle around (xc3x97)}xcex9(kxe2x88x921)(x)] and xcexa9(k)(x)=xcexa9(kxe2x88x922)(x)xe2x88x92[Q(k)(x){circle around (xc3x97)}xcexa9(kxe2x88x921)(x)], where Q(k)(x)=xcexa9(kxe2x88x922)(x){circle around (÷)}xcexa9(kxe2x88x921)(x). Initial values used at k=1 should be xcex9(xe2x88x921)(x)=0, xcex9(0)(x)=1, xcexa9(xe2x88x921)(x)=x2t, and xcexa9(0)(x)=S(x). The logic to calculate should iterate until the degree of the of xcexa9(kxe2x88x921)(x) less than t. The present invention can be practiced with only one multiplier per first cell and no multipliers in the second or third cells. Moreover, the first cells include logic which exercises the multiplier only once to calculate said difference.
A further aspect of the present invention is a method and device for decoding Reed-Solomon (N, K) encoded messages with m-bit symbols, where N less than =2mxe2x88x921 and 2t=Nxe2x88x92K, including an array of first cells, logically partitioned into xcexa9(ixe2x88x922) and xcex9(ixe2x88x922) cells, said first cells coupled to adjacent first cells, an array of second cells, logically partitioned into xcexa9(ixe2x88x921) and xcex9(ixe2x88x921) cells, said second cells coupled to corresponding and next higher order first cells and to adjacent second cells, an array of third cells, said third cells coupled to the corresponding first and second cells and to adjacent third cells, a shared divider coupled to first cells, logic associated with the first, second and third cells to calculate a quotient q=xcexa9(ixe2x88x922)/xcexa9(ixe2x88x921) and a remainder of the quotient, logic associated with the first, second and third cells to calculate xcexa9(i)=xcexa9(ixe2x88x922)xe2x88x92Q(k)xcexa9(ixe2x88x921) and logic associated with the first, second and third cells to calculate xcex9(i)=xcex9(ixe2x88x922)xe2x88x92Q(k)xcex9(ixe2x88x921).
An additional aspect of the present invention is a method and device for evaluating a t+1-term error location polynomial and a t-term error evaluator polynomial useful for decoding Reed-Solomon (N, K) encoded messages with m-bit symbols, where N less than =2mxe2x88x921 and 2t=Nxe2x88x92K, including an array of xcexa9 cells initialized with an error location polynomial, an array of xcex9 cells initialized with an error evaluator polynomial, said array of xcex9 cells including xcex9even and xcex9odd sub arrays, a first constant factor generator coupled to the highest order cell of the xcexa9 array, a second constant factor generator coupled to the highest order cell of the xcex9even and xcex9odd sub arrays, logic to pass first constant factors values serially through the xcexa9 array cells and to evaluate xcexa9(x) at values of xk generated by the first constant factor generator, where k is an index of iteration, and logic to pass second constant factors serially through both the xcex9even array and the xcex9odd array and to evaluate xcex9even(x2) and xcex9odd(x2) at values of x2k generated by the second constant factor generator. This aspect of the invention may further include logic evaluate xcex9(x)=xcex9even(x2)+x xcex9odd(x2) at x2k and, when xcex9(x)=0 to evaluate E(x)=xcexa9(x)/xcex9odd(x2).
When various aspects of the present invention are combined, the method and device may include a device for decoding Reed-Solomon (N, K) encoded messages with m-bit symbols, where N less than =2mxe2x88x921 and 2t=Nxe2x88x92K, comprising syndrome calculation means for calculating a syndrome polynomial of a received Reed-Solomon (N, K) encoded message, an array of 2t+1 first cells, logically partitioned into xcexa9(ixe2x88x922) and xcex9(ixe2x88x922) cells, said first coupled to adjacent first cells, an array of second cells, logically partitioned into xcexa9(ixe2x88x921) and xcex9(ixe2x88x921) cells, said second cells receiving the syndrome polynomial from the syndrome calculation means and being coupled to the corresponding and next higher order first cells and to adjacent second cells, an array of third cells, said third cells coupled to the first and second cells and to adjacent the third cells, a shared divider coupled to the first and third cells, logic associated with the first, second and third cells to apply Euclid""s algorithm and generate an error location and an error value polynomial, Chien search means for identifying elements of GF(2m) which are roots of the error location polynomial, coupled to the logic to generate an error location polynomial, and error evaluation means for evaluating the error value polynomial at roots of the error location polynomial, coupled to the logic to generate an error value polynomial and to the Chien search means.